package org.TheSubject;

import sun.misc.Unsafe;

import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 */
public class Solution23OfHot {
    private static class ListNode  {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode tail=dummy;
        PriorityQueue<ListNode> listNodes = new PriorityQueue<>(
                (o1, o2) -> o1.val-o2.val
        );
        for (ListNode l :lists) {
            if (l!=null){
                listNodes.offer(l);
            }
        }
        while (!listNodes.isEmpty()){
            ListNode newNode = listNodes.poll();
            tail.next=newNode;
            tail=tail.next;
            if(newNode.next!=null){
                listNodes.offer(newNode.next);
            }
        }
        return dummy.next;
    }


    public static void main(String[] args) {
        try {
            Thread.sleep(30000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        ListNode listNode = new ListNode(1);
        listNode.next=new ListNode(5);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode[] listNodes=new ListNode[3];
        listNodes[0]=listNode;listNodes[1]=listNode1;listNodes[2]=listNode2;
        Solution23OfHot solution23OfHot = new Solution23OfHot();
        ListNode listNode3 = solution23OfHot.mergeKLists(listNodes);
        System.out.println(listNode);
    }
}
